package study1;

import java.util.*;

public class InorderTraversal {
    static class TreeNode {
        public int val;         // 节点存储的字符值
        public TreeNode left;    // 左子节点引用
        public TreeNode right;   // 右子节点引用

        public TreeNode(int val) {
            this.val = val;      // 构造函数初始化节点值
        }
    }


    /**
     *
     思路与算法
        首先我们需要了解什么是二叉树的中序遍历：按照访问左子树——根节点——右子树的方式遍历这棵树，而在访问左子树或者右子树的时候我们按照同样的方式遍历，
     直到遍历完整棵树。因此整个遍历过程天然具有递归的性质，我们可以直接用递归函数来模拟这一过程。
        定义 inorder(root) 表示当前遍历到 root 节点的答案，那么按照定义，我们只要递归调用 inorder(root.left) 来遍历 root 节点的左子树，
     然后将 root 节点的值加入答案，再递归调用inorder(root.right) 来遍历 root 节点的右子树即可，递归终止的条件为碰到空节点。

     复杂度分析
        时间复杂度：O(n)，其中 n 为二叉树节点的个数。二叉树的遍历中每个节点会被访问一次且只会被访问一次。
        空间复杂度：O(n)。空间复杂度取决于递归的栈深度，而栈深度在二叉树为一条链的情况下会达到 O(n) 的级别。


     * */
    // 递归方法实现中序遍历
    /**
     算法逻辑：
     模拟中序遍历的自然过程（左子树 → 根节点 → 右子树），通过递归隐式维护调用栈。

     执行过程：
     1. 若当前节点为空，直接返回
     2. 递归遍历左子树
     3. 将当前节点值加入结果集
     4. 递归遍历右子树

     变量分析：
        res：存储遍历结果的动态数组
        root：当前递归处理的节点（随递归深度变化）


     适用场景：
        树深度较小（避免栈溢出）
        代码简洁性优先
        时间复杂度：O(n)，每个节点被访问一次（n 为节点总数）。
        空间复杂度：O(h)（h为树高。最坏O(n)最坏情况下（树退化为链表），递归调用栈深度为 n。

     ）
     * */

    /*为什么分开两个方法？
        公共方法负责初始化结果列表，隐藏递归细节。
        私有方法专注递归逻辑，避免用户直接调用递归过程。*/
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();// 创建一个空的 ArrayList 用于存储遍历结果。
        inorder(root, res);// 调用私有递归方法 inorder，传入根节点 root 和结果列表 res
        return res;// 返回存储了遍历结果的列表。此时列表已按中序遍历顺序填充了节点的值
    }

    private void inorder(TreeNode root, List<Integer> res) {
        if (root == null) { // 1. 终止条件,如果当前节点为空，直接返回。递归必须有一个终止点。空节点表示子树已遍历完毕或树为空，防止无限递归和空指针异常。
            return;
        }
        inorder(root.left, res); // 2. 遍历左子树
        res.add(root.val); // 3. 访问根节点,将当前节点的值 root.val 添加到结果列表。
        inorder(root.right, res); // 4. 遍历右子树
    }


    /**
     方法二：迭代法（显式栈）

     算法逻辑：
     用栈显式模拟递归过程，手动控制节点访问顺序。

     执行过程：
     1. 当前节点非空时，持续压入左子节点（深入左子树）
     2. 当左子节点为空时，弹出栈顶节点并访问
     3. 转向该节点的右子树，重复上述过程

     变量分析：
        stk：模拟递归的栈（存储未处理的节点）
        res：结果集
        root：动态指向当前处理的节点


     适用场景：
        树深度较大（避免递归栈溢出）
        需要显式控制遍历过程
        时间复杂度：O(n)，空间复杂度：O(h)（最坏O(n)）
     * */
    // 迭代实现（显式栈）
    public List<Integer> inorderTraversal2(TreeNode root) {
        List<Integer> res = new ArrayList<>();      // 1. 创建结果列表，存储遍历结果
        Deque<TreeNode> stk = new LinkedList<>();   // 2. 使用双端队列模拟栈（Java推荐用Deque代替Stack）

        while (root != null || !stk.isEmpty()) {    // 3. 循环条件：当前节点非空 或 栈非空
            // 深入左子树直至叶子节点
            while (root != null) {                  // 4. 当前节点非空时，持续向左下深入
                stk.push(root);                     // 5. 当前节点入栈（后续回溯用）
                root = root.left;                   // 6. 移动到左子节点
            }
            root = stk.pop();       // 回溯到父节点，  // 7. 弹出栈顶节点（当前最左侧节点）
            res.add(root.val);     // 访问节点值
            root = root.right;      // 转向右子树
        }
        return res;
    }





    /**
     方法三：Morris遍历

     算法逻辑：
     利用叶子节点的空指针建立临时回退链路，实现空间复杂度O(1)的遍历。

     执行过程：
     1. 当前节点存在左子树：
        找到左子树的最右节点（中序前驱）
        若前驱的右指针为空：将其指向当前节点（建立临时链路），转向左子树
        若前驱的右指针指向当前节点：断开链路，访问当前节点，转向右子树
     2. 当前节点无左子树：
        直接访问当前节点
        转向右子树

     变量分析：
        predecessor：当前节点的中序前驱节点
        res：结果集
        root：动态移动的当前节点

     适用场景：
        严格限制O(1)空间的场景
        允许临时修改树结构（遍历后自动恢复）
        时间复杂度：O(n)，空间复杂度：O(1)
     * */
    public List<Integer> inorderTraversal3(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        TreeNode predecessor = null;

        while (root != null) {
            if (root.left != null) {
                // predecessor 节点就是当前 root 节点向左走一步，然后一直向右走至无法走为止
                predecessor = root.left;
                while (predecessor.right != null && predecessor.right != root) {
                    predecessor = predecessor.right;
                }

                // 让 predecessor 的右指针指向 root，继续遍历左子树
                if (predecessor.right == null) {
                    predecessor.right = root;
                    root = root.left;
                }
                // 说明左子树已经访问完了，我们需要断开链接
                else {
                    res.add(root.val);
                    predecessor.right = null;
                    root = root.right;
                }
            }
            // 如果没有左孩子，则直接访问右孩子
            else {
                res.add(root.val);
                root = root.right;
            }
        }
        return res;
    }



    /*
方法	        空间复杂度	        优势	                        劣势	                         适用场景
递归法	      O(h)	    代码简洁，符合自然思维	        递归深度过大时可能栈溢出	        树高度较小或系统栈空间充足
迭代法	      O(h)	    避免递归栈溢出，过程可控	        需显式维护栈	                深度较大的树或需避免递归的场景
Morris遍历	  O(1)	    极致空间优化，无额外数据结构	    修改树结构，逻辑复杂	        空间严格受限或禁止使用栈的场景


核心选择建议：
    优先考虑迭代法（平衡性能和安全性）
    空间敏感场景选择Morris遍历
    小规模数据用递归法
* */


    /**
     方法四：线索二叉树法（Threaded Binary Tree）
     算法逻辑：
     通过将空指针改为线索（指向中序前驱或后继），实现无栈遍历。需预先处理树结构。

     执行过程：
     1. 建立临时线索：将左子树的最右节点指向当前节点
     2. 沿线索回溯访问节点
     3. 遍历后移除线索（可选）

     适用场景：
        需要反复遍历同一棵树
        允许永久修改树结构
        时间复杂度：O(n)，空间复杂度：O(1)（永久线索化后）
     * */
    // 线索二叉树实现 (需修改树节点结构)
    static class ThreadedTreeNode {
        int val;
        ThreadedTreeNode left, right;
        boolean isThreaded;  // 标记右指针是否为线索

        public ThreadedTreeNode(int val) {
            this.val = val;
        }
    }

    public List<Integer> inorderThreaded(ThreadedTreeNode root) {
        List<Integer> res = new ArrayList<>();
        ThreadedTreeNode curr = root;

        while (curr != null) {
            if (curr.left == null) {
                res.add(curr.val);
                curr = curr.isThreaded ? null : curr.right;
            } else {
                // 找到前驱节点
                ThreadedTreeNode pre = curr.left;
                while (pre.right != null && pre.right != curr) {
                    pre = pre.right;
                }

                if (pre.right == null) {
                    pre.right = curr;          // 建立线索
                    pre.isThreaded = true;
                    curr = curr.left;
                } else {
                    res.add(curr.val);
                    pre.right = null;          // 移除线索
                    pre.isThreaded = false;
                    curr = curr.right;
                }
            }
        }
        return res;
    }


    /**
     方法五：颜色标记法（迭代变种）
     算法逻辑：
     用栈存储节点+状态标记，统一三种遍历方式的代码结构。

     执行过程：
     1. 白色（0）：未访问的节点
     2. 灰色（1）：已访问的节点
     3. 按"右→根→左"顺序入栈（中序=左→根→右）

     压栈顺序（逆序遍历顺序）：右子树 → 根节点(状态1) → 左子树
     出栈顺序（实际遍历顺序）：
        左子节点最先弹出（状态0），触发其子树的压栈
        当左子树处理完毕后，根节点(状态1)弹出并记录值
        最后处理右子树


     算法特点与适用场景
     1. 统一框架：三种遍历使用相同结构，仅改变压栈顺序
     2. 显式状态管理：避免递归隐式栈的不可控性
     3. 空间复杂度：O(h)（h为树高），优于递归栈溢出风险
     4. 适用场景：
        需要避免递归的深度限制（大数据量树）
        需灵活切换遍历方式的场景（如树结构编辑器）
        需显式控制栈的操作（如自定义遍历中断）


     * */

    public List<Integer> inorderTraversal4(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;

        Deque<Object[]> stack = new ArrayDeque<>();
        stack.push(new Object[]{root, 0}); // 根节点初始状态0入栈

        while (!stack.isEmpty()) {
            Object[] item = stack.pop();
            TreeNode node = (TreeNode) item[0];
            int status = (Integer) item[1];

            if (status == 1) {
                result.add(node.val); // 状态1：记录节点值
            } else {
                // 状态0：按【右子节点 → 当前节点(状态1) → 左子节点】逆序压栈
                if (node.right != null) {
                    stack.push(new Object[]{node.right, 0});
                }
                stack.push(new Object[]{node, 1}); // 当前节点标记为已访问
                if (node.left != null) {
                    stack.push(new Object[]{node.left, 0});
                }
            }
        }
        return result;
    }


}

